package Javafoundation;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
public class Gragh2 {
    private List<Vertex> vertices;
    private int edgeCount;
    private List<Vertex> depthFirstResult;
    private List<Vertex> breadthFirstResult;

    public void breadthFirstVisit(char beginLabel){

        Vertex origin=this.getVertexByChar(beginLabel);
        if(origin==null)return;
        List<Vertex> queue=new LinkedList<Vertex>();
        origin.setVisited(true);
        queue.add(origin);
        breadthFirstResult.add(origin);
        Vertex curVertex=null;
        while(!queue.isEmpty()){
            curVertex=queue.remove(0);
            while(curVertex.getFirstUnvisitedNeighbor()!=null){
                Vertex tmpVertex=curVertex.getFirstUnvisitedNeighbor();
                tmpVertex.setVisited(true);
                queue.add(tmpVertex);
                breadthFirstResult.add(tmpVertex);
            }

        }
        printVertexList(breadthFirstResult);
    }

    public void depthFirstVisit(char beginLabel){

        Vertex origin=this.getVertexByChar(beginLabel);
        if(origin==null)return;
        Stack<Vertex> stack=new Stack<Vertex>();
        origin.setVisited(true);
        stack.push(origin);
        depthFirstResult.add(origin);
        Vertex curVertex=null;
        while(!stack.isEmpty()){
            curVertex=stack.peek();
            Vertex tmpVertex=curVertex.getFirstUnvisitedNeighbor();
            if(tmpVertex!=null){
                tmpVertex.setVisited(true);
                depthFirstResult.add(tmpVertex);
                stack.push(tmpVertex);
            }else{
                stack.pop();
            }
        }
        printVertexList(depthFirstResult);
    }

    //getShortestPath.Base on breadthFirstVisit.the edge has no weight.
    public double getShortestPath(char beginLabel,char endLabel,Stack<Vertex> stack){
        resetVertices();
        Vertex begin=this.getVertexByChar(beginLabel);
        Vertex end=this.getVertexByChar(endLabel);
        begin.setVisited(true);
        List<Vertex> queue=new LinkedList<Vertex>();
        queue.add(begin);
        boolean done=false;
        while(!done&&!queue.isEmpty()){
            Vertex curVertex=queue.remove(0);
            while(!done&&curVertex.getFirstUnvisitedNeighbor()!=null){
                Vertex tmpVertex=curVertex.getFirstUnvisitedNeighbor();
                tmpVertex.setVisited(true);
                double  tmpCost=curVertex.getCost()+1;
                tmpVertex.setPreviousVertex(curVertex);
                tmpVertex.setCost(tmpCost);
                queue.add(tmpVertex);
                if(tmpVertex.equals(end)){
                    done=true;
                }
            }
        }
        double pathLength=end.getCost();
        //find the path.traverse back from end
        while(end!=null){
            stack.push(end);
            end=end.getPreviousVertex();
        }
        return pathLength;
    }

    public boolean addEdge(char beginLabel,char endLabel,double weight){
        int beginIndex=vertices.indexOf(new Vertex(beginLabel));
        int endIndex=vertices.indexOf(new Vertex(endLabel));
        Vertex beginVertex=vertices.get(beginIndex);
        Vertex endVertex=vertices.get(endIndex);
        boolean result=beginVertex.connect(endVertex,weight);
        edgeCount++;
        return result;
    }
    public boolean addEdge(char beginLabel,char endLabel){
        return addEdge(beginLabel,endLabel,0);
    }
    public boolean addVertex(char label){
        boolean result=false;
        Vertex newVertex=new Vertex(label);
        if(!vertices.contains(newVertex)){
            vertices.add(newVertex);//reject duplicate vertex
            result=true;
        }
        return result;
    }
    public void printVertexList(List<Vertex> list){
        for(int i=0,len=list.size();i<len;i++){
            Vertex vertex=list.get(i);
            System.out.print(vertex.getLabel()+" ");
        }
        System.out.println();
    }

    public void resetVertices(){
        for(int i=0,len=vertices.size();i<len;i++){
            Vertex vertex=vertices.get(i);
            vertex.setPreviousVertex(null);
            vertex.setVisited(false);
            vertex.setCost(0);
        }
    }

    public Vertex getVertexByChar(char target){
        Vertex vertex=null;
        for(int i=0,len=vertices.size();i<len;i++){
            vertex=vertices.get(i);
            Character xx=vertex.getLabel();
            if(xx.charValue()==target){
                return vertex;
            }
        }
        return vertex;
    }

    public Gragh2(){
        vertices=new ArrayList<Vertex>();
        edgeCount=0;
        depthFirstResult=new ArrayList<Vertex>();
        breadthFirstResult=new ArrayList<Vertex>();
    }



    public static void main(String[] args) {

        Gragh2 graph=createGapth();
        graph.depthFirstVisit('7');//depthFirstVisit,start with '7'
        graph.resetVertices();
        graph.breadthFirstVisit('0');//breadthFirstVisit,start with '0'

        //shortest path
        Stack<Vertex> pathStack=new Stack<Vertex>();
        //from '0' to '7'.
        double pathLength=graph.getShortestPath('0','7',pathStack);
        System.out.println(pathLength);
        while(!pathStack.isEmpty()){
            Vertex vertex=pathStack.pop();
            System.out.print(vertex.getLabel()+" ");
        }

        //BasicGraphInterface<String> airMap=new UndirectedGraph<String>();
        //airMap.

    }

    public static Gragh2 createGapth(){

        Gragh2 graph=new Gragh2();
        graph.addVertex('0');
        graph.addVertex('1');
        graph.addVertex('2');
        graph.addVertex('3');
        graph.addVertex('4');
        graph.addVertex('5');
        graph.addVertex('6');
        graph.addVertex('7');

        graph.addEdge('0','4');
        graph.addEdge('0','3');
        graph.addEdge('0','1');

        graph.addEdge('1','4');
        graph.addEdge('1','2');
        graph.addEdge('1','0');

        graph.addEdge('2','5');
        graph.addEdge('2','1');

        graph.addEdge('3','6');
        graph.addEdge('3','0');

        graph.addEdge('4','6');
        graph.addEdge('4','1');
        graph.addEdge('4','0');

        graph.addEdge('5','2');

        graph.addEdge('6','7');
        graph.addEdge('6','4');
        graph.addEdge('6','3');

        graph.addEdge('7','6');

        return graph;
    }
}


class Vertex{
    private char label;
    private List<Edge> edgeList;
    private boolean isVisited;
    private Vertex previousVertex;//use it in the method-'getShortestPath()'
    private double cost;//the cost from beginning to this vertex

    public Vertex(char label){
        this.label=label;
        edgeList=new ArrayList<Edge>();
        isVisited=false;
        previousVertex=null;
        cost=0;
    }
    public boolean isVisited(){
        return isVisited;
    }
    public void visit(){
        System.out.println(this.label);
        this.isVisited=true;
    }

    public void setPreviousVertex(Vertex vertex){
        this.previousVertex=vertex;
    }
    public void setVisited(Boolean isVisited){
        this.isVisited=isVisited;
    }
    public void setCost(double cost){
        this.cost=cost;
    }
    public Vertex getFirstNeighbor(){
        Vertex neighbor=this.edgeList.get(0).endVertex;
        return neighbor;
    }
    public char getLabel(){
        return this.label;
    }

    public double getCost(){
        return this.cost;
    }
    public Vertex getPreviousVertex(){
        return this.previousVertex;
    }
    public Vertex getFirstUnvisitedNeighbor(){
        Vertex unVisitedNeighbor=null;
        for(int i=0,len=edgeList.size();i<len;i++){
            Vertex vertex=edgeList.get(i).endVertex;
            if(!vertex.isVisited){
                unVisitedNeighbor=vertex;
                break;
            }
        }
        return unVisitedNeighbor;
    }
    public boolean equals(Object object){
        boolean result=false;
        if(this==object)return true;
        if(object instanceof Vertex){
            Vertex otherVertex=(Vertex)object;
            result=this.label==otherVertex.label;
        }
        return result;
    }
    public boolean connect(Vertex endVertex,double weight){

        boolean result=false;//result=true if successful

        if(!this.equals(endVertex)){//connections should occur in different Vertices
            boolean isDuplicateEdge=false;
            List<Edge> edgeList=this.edgeList;
            if(edgeList.contains(endVertex)){
                isDuplicateEdge=true;
            }
            if(!isDuplicateEdge){
                //endVertex.previousVertex=this;
                edgeList.add(new Edge(endVertex,weight));
                result=true;
            }
        }

        return result;
    }

    public boolean hasNeighbor(){
        return !edgeList.isEmpty();
    }
    protected  class Edge{
        //A-->B,then the "outerClass" which invokes the method "getEndVertex"
        //is "A",the "endVertex" is "B"
        private Vertex endVertex;
        private double weight;

        protected Edge(Vertex endVertex,double weight){
            this.endVertex=endVertex;
            this.weight=weight;
        }
        protected Vertex getEndVertex(){
            return endVertex;
        }
        protected double getWeight(){
            return weight;
        }

    }
}
